The invention is generally related to integrated circuits and integrated circuit design, and in particular to automated buffer insertion during physical design of integrated circuits.
Electronic integrated circuits, or xe2x80x9cchipsxe2x80x9d have become significantly more complex as circuit fabrication technologies have improved. It is not uncommon for integrated circuits to incorporate hundreds of millions of transistors, with a comparable number of interconnects, or signal paths, integrated together onto a single piece of silicon substrate no larger than the size of a coin. In addition, often the same functionality that once required multiple chips can now be integrated onto the same chip, a concept often referred to as xe2x80x9csystem-on-chipxe2x80x9d technology.
The design of integrated circuits has likewise become more difficult as complexity has increased. Whereas early chips were often designed gate by gate, more advanced integrated circuits incorporating millions of gates represent too much of an undertaking for early design methodologies. Likewise, another important aspect of integrated circuit design is that of testing and verifying an integrated circuit design, both from the standpoint of verifying that a design will logically operate as intended, and of ensuring that a design will comply with the physical limitations that are inherent in any integrated circuit, i.e., to ensure that all timing and delay constraints are met.
As a result, a variety of software design applications, or tools, have been developed to assist designers with designing and testing integrated circuits.
Generally when utilizing these tools, the overall design process is represented by two stages. The first stage is referred to as logic design, where the desired functional operation of an integrated circuit is initially defined and tested. The second stage is referred to as physical design, where the logic design created during the logic design stage is processed to select actual circuit components to implement the functions defined in the logic design, and to lay out the components on an integrated circuit and route interconnects therebetween. The interconnections between circuit elements are often referred to as nets, and the nets are generally routed afer placement of circuit components at specific locations on an integrated circuit.
One important parameter that must be accounted for during the design of an integrated circuit is that of timing. In particular, due to factors such as resistance, capacitance, switching delays, etc., signals that are propagated through an integrated circuit require some finite amount of time to reach various destinations. In any given integrated circuit design, however, often signals must reach destinations within a certain time frame (typically before the end of a clock cycle), lest data be missed due its late arrival at a destination. Timing particularly becomes troublesome for relatively long interconnects, as the inherent resistance and capacitance of such interconnects may delay the arrival of a signal on a long interconnect beyond that which is acceptable under the normal operating conditions for an integrated circuit.
Timing is often accounted for in both the logic and physical design stages of an integrated circuit. However, during the logic design stage, timing parameters for the various nets in a design are typically estimated using formulas, and these estimates are often not particularly accurate. Timing analysis is also performed during the physical design stage, and a developer may be required to refine a design after timing analysis if it is determined during the physical design stage that timing parameters are not acceptable.
Given the rather gross estimates made during the logic design stage, it is not uncommon for an integrated circuit design to meet timing constraints in the logic design stage, but not meet the timing constraints after layout and routing during the physical design stage. As a result, various types of post-layout optimization algorithms are often utilized to address many of these timing problems in an automated manner. By doing so, a designer may not be required to return to the logic design stage for manual refinements of a design, which can substantially simplify the design process.
One such type of post-layout optimization is automated buffer insertion. In particular, the addition of one or more inverting or non-inverting buffers into a relatively long interconnect in an integrated circuit design will typically improve the timing parameters for that interconnect due to reduced load, reduced delay, and reduced slew, and often without altering the overall length of an interconnect. Thus, by the selective addition of buffers to a design, often previously non-compliant designs can be optimized in an automated manner to bring those designs into compliance with timing constraints.
Most conventional automated buffer insertion algorithms place buffers using a pre-existing routing tree. A routing tree is typically created for each xe2x80x9cnetxe2x80x9d in a design, i.e., for each interconnect between a signal source and one or more signal sinks. In many instances, each routing tree is configured as a Steiner tree, which attempts to generate the shortest orthogonal path or xe2x80x9croutexe2x80x9d between any source and its sinks. Additional points, known as Steiner points, are typically added to routes so that, between any non-orthogonal nodes along a route, interconnect segments are routed in a vertical-horizontal or horizontal-vertical manner, thus creating one or more L-shaped spans between a source and its sinks.
One problem associated with many conventional automated buffer insertion algorithms, however, typically arises when a relatively large number of similar nets need to be routed, with all of the sources for those nets disposed in one small region and all of the sinks for those nets disposed in another small region, e.g., for a bus or similar multi-signal interface. In such an instance, where all of the Steiner routes are similar, the locations for the buffers added by a conventional automated buffering insertion process will typically be located in approximately the same locations. Then, once the buffers are placed, the subsequent routing of interconnects is substantially constrained, causing difficulties associated with routing a large number of interconnects through the same general region of an integrated circuit.
Put another way, without the buffers, a router is free to select any orthogonal path to traverse from each source to each corresponding sink. Moreover, as tracks fill, the router can use different equivalent routes. However, after buffers are inserted, the router is forced to follow nearly the same path for all nets, since it must work its way through the buffers. As a result, the placement of the buffers essentially defines the routes. Consequently, substantial congestion may arise in particular regions of an integrated circuit design due to the placement of buffers in close proximity to one another. Conventional automated buffer insertion algorithms have thus been found to cause significant congestion in many integrated circuit designs in the instances where a number of relatively long interconnects are required to be routed between roughly the same regions on an integrated circuit design.
Therefore, a significant need exists in the art for a manner of relieving congestion in an integrated circuit design caused by the placement of buffers as a result of automated buffer insertion performed during post-layout optimization of an integrated circuit design.
The invention addresses these and other problems associated with the prior art by providing an apparatus, program product and method in which a congestion relief algorithm is used in connection with automated buffer insertion to relieve potential congestion during post-layout optimization of an integrated circuit design. The congestion relief algorithm is utilized to manipulate a plurality of L-shaped spans defined in a routing tree, and is configured to apply the congestion relief algorithm to at least a first L-shaped span among the plurality of L-shaped spans by rerouting the first L-shaped span at least partially within a rectangular area bounded by the first L-shaped span.
A wide variety of algorithms may be used to reroute L-shaped spans at least partially through the respective rectangular areas bounded by such spans. For example, in the illustrated embodiments discussed below, an intermediate point is selected for an L-shaped span, and is positioned so as to reside within the rectangular area for the span. Two sub-spans are then defined, extending between the original end points of the span and the intermediate point. Each sub-span is then configured to be routed in either a vertical-horizontal routing or a horizontal-vertical routing.
When the aforementioned congestion relief algorithm is applied to one or more L-shaped spans of a routing tree, and particularly when such an algorithm is applied to multiple routing trees in an integrated circuit design, the potential for congestion to arise due to the insertion of buffers is substantially decreased. In addition, while other automated buffer insertion algorithms may be used in connection with the herein-described congestion relief algorithm, when an automated buffer insertion algorithm that places buffers on preexisting routing trees is utilized, the aforementioned congestion relief algorithm may be used to generate an optimized routing tree to ensure that buffers are more widely dispersed throughout an integrated circuit design by such an automated buffer insertion algorithm. As a result, subsequent automated routing of interconnects in the design experiences reduced congestion-related routing problems.
These and other advantages and features, which characterize the invention, are set forth in the claims annexed hereto and forming a further part hereof. However, for a better understanding of the invention, and of the advantages and objectives attained through its use, reference should be made to the Drawings, and to the accompanying descriptive matter, in which there is described exemplary embodiments of the invention.